#include "stdafx.h"
#include <iostream>

#include <time.h>   
#include <ctime>
#include <stdio.h>      
#include <stdlib.h>   

static void siftDown(int *a, int i, int j);


int* makeArray(int size)
{

	int *a = new int[size];
	//////////////////////////////////

	srand((unsigned int)time(NULL));

	for (int i = 0; i < size; i++)
	{
		// a[i]=(rand() % 100) * (rand() % 10) + rand() % 1000;
		a[i] = (rand() % 100000);

	}
	return a;
}


/////////////////////////////////////////////////////////////////////////////////////////////
static void HeapSort(int * a,int size)
{
	int i;
	int temp;

	for (i = (size / 2) - 1; i >= 0; i--)
	{
		siftDown(a, i, size);
	}

	for (i = size - 1; i >= 1; i--)
	{
		temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		siftDown(a, 0, i - 1);
	}
}

static void siftDown(int *a, int i, int j)
{
	bool done = false;
	int maxChild;
	int temp;

	while ((i * 2 < j) && (!done))
	{
		if (i * 2 == j)
			maxChild = i * 2;
		else if (a[i * 2] > a[i * 2 + 1])
			maxChild = i * 2;
		else
			maxChild = i * 2 + 1;

		if (a[i] < a[maxChild])
		{
			temp = a[i];
			a[i] = a[maxChild];
			a[maxChild] = temp;
			i = maxChild;
		}
		else
		{
			done = true;
		}
	}
}


///////////////////////////////////////

int _tmain(int argc, _TCHAR* argv[])
{
	const int size = 40;

	int *a = makeArray(size);
	HeapSort(a, size);

	for (int i = 0; i < size; i++){
		std::cout << a[i] << "\n";


	}


	return 0;
}

